package com.wp.algorithm.a1_dynamic_programing.code;

import java.util.ArrayList;
import java.util.List;

/**
 * @author wangpeng
 * @description ******
 * @date 2021/11/11 16:13
 */
public class Test2Coin {

    private final static int[] array = {1,2,5,10};

    public static void main(String[] args) {

        int amount = 148;
        /**
         * dp(n) = -1 ; n<0
         *       = 0  ; n=0
         *       = min(dp(n-coin)) +1 ; n>0
         */
        System.out.println(coinChange(amount));
    }

    private static int coinChange (int amount) {
        if(amount<0){
            return -1;
        }
        if(amount==0){
            return 0;
        }

        int num = 0;

        for (int e :
                array) {
            int remains = coinChange(amount-e);
            if(remains==0){
                num++;
            }

        }

        return 0;
    }

}
